package com.woldier.algorithm.hashing;

import java.io.Serializable;
import java.util.*;

/**
 * description 字母异位词分组
 * <p>
 * 给定一个字符串数组 strs ，将 变位词 组合在一起。 可以按任意顺序返回结果列表。
 * <p>
 * 注意：若两个字符串中每个字符出现的次数都相同，则称它们互为变位词。
 * <p>
 * 示例 1:
 * <p>
 * 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
 * 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
 * 示例 2:
 * <p>
 * 输入: strs = [""]
 * 输出: [[""]]
 * 示例 3:
 * <p>
 * 输入: strs = ["a"]
 * 输出: [["a"]]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= strs.length <= 104
 * 0 <= strs[i].length <= 100
 * strs[i] 仅包含小写字母
 * <p>
 * ===========================================================
 *
 * @author: woldier wong
 * @date: 2023/12/25 15:10
 */
public class Leetcode_LCR033_GroupAnagrams {
    /**
     * description
     * <p>
     * 算法思想是, 对于每一个String, 其每个字符都转换为数字, 并且进行加法, 因为 无论bat还是abt, 它们的字符数组相加的值都是相同的
     * <p>
     * 想法1:本方法灵感来源于String 的hash算法, 在String的hash中, 每个字符都加上了一个位置偏置, 以防止 bat, 和 abt 的冲突, 但是在这里我们恰恰是利用了这一点,但是需注意的是 cas 也可以产生相同的hash码,怎么区分它是需要考虑的.
     * <p>
     * 想法2: 将字符串转为按照字符升序排列,让后放入map中
     * <p>
     * 想法3: 基于第二种思想 ,建立一个数组[0,0,0,.....,0] 长度为26 让后索引位置记录对应单词出现的次数
     * <p>
     * 如baat 那么对应的数据是[2,2,0,...,0] 让后将其作为key 放入map中
     *
     * @param strs 输入的单词
     * @return java.util.List<java.util.List < java.lang.String>>   分组后的结果
     * @author: woldier wong
     * @date: 2023/12/25 15:15
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> keyMap = new HashMap<>();
        Arrays.stream(strs).forEach(
                e -> {
                    char[] charArray = e.toCharArray(); //转char数组
                    Arrays.sort(charArray);  //排序
                    String key = String.valueOf(charArray);
                    keyMap.compute(key, (k, v) -> {
                                if (v == null) {
                                    return new ArrayList<>(Collections.singletonList(e));
                                } else {
                                    v.add(e);
                                    return v;
                                }
                            }
                    );

                }
        );
        return
                new ArrayList<>(keyMap.values());
    }

    class ArrayKey{
        int[] index ;

        public ArrayKey(String s) {
            index = new int[26];
            char start = 'a';
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                int i1 = (int) c - (int) start;
                index[i1] += 1;
            }
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            ArrayKey arrayKey = (ArrayKey) o;
            return Arrays.equals(index, arrayKey.index);
        }

        @Override
        public int hashCode() {
            return Arrays.hashCode(index);
        }
    }

    public List<List<String>> groupAnagramsV2(String[] strs) {
        HashMap<ArrayKey, List<String>> keyMap = new HashMap<>();
        Arrays.stream(strs).forEach(
                e -> {
                    ArrayKey key = new ArrayKey(e);
                    keyMap.compute(key, (k, v) -> {
                                if (v == null) {
                                    return new ArrayList<>(Collections.singletonList(e));
                                } else {
                                    v.add(e);
                                    return v;
                                }
                            }
                    );

                }
        );
        return
                new ArrayList<>(keyMap.values());
    }

}
